package org.example.sword2offer.primary;

import java.util.Arrays;

/**
 * @author: lynn
 * @Descript: {100、50、20、10、5、2、1} ，假设商品价格N，求最少张数，动态规划解 leetcode 322
 * 解法连接:  https://www.bilibili.com/video/BV1cT4y1w7Ct?from=search&seid=2941701713750152698
 * @date: 2021/6/27 21:40
 * @version: 1.0
 */
public class Q74_FindLessMoneyByDP {
    public static void main(String[] args) {
        int[] moneyArray={100,50,20,10,5,2,1};
        int payMoney=7;
        Q74_FindLessMoneyByDP findLessMoney=new Q74_FindLessMoneyByDP();
        System.out.println(findLessMoney.coinChange(moneyArray,payMoney));
        System.out.println(findLessMoney.coinChangeEasy(moneyArray,payMoney));
    }
    public int coinChange(int[] coins, int amount) {//fixme 找零钱问题，用动态规划解法
        //fixme 初始化数组dp,全部元素初始化为 -1,金额为0的初始化为0
        int[] dp=new int[amount+1];
        Arrays.fill(dp,-1);
        dp[0]=0;// dp[i] 代表最优解
        for(int i=1;i<=amount;i++){//fixme 变量i从1循环到amount,依次计算金额1到amount的最优解
            //fixme 对于每个金额i，使用变量j遍历面值coins数组
            for(int j=0;j<coins.length;j++){
                //fixme 所有小于等于i的面值coin[j],如果金额i-coins[j]有最有解 6=coin(1)+dp[5] 或者 6=coin(5)+dp[1]
                if(coins[j]<=i && dp[i-coins[j]]!=-1){
                    //fixme 如果当前金额还未计算，或者dp[i]比正在计算的最优解大
                    //fixme coins=1,2,3,5,7,10  dp[5]=1+dp[4],2+dp[3],3+dp[2],5+dp[0]
                    if(dp[i]==-1||dp[i]>dp[i-coins[j]]+1){//fixme 这个1代表面值是一次
                        dp[i]=dp[i-coins[j]]+1;//fixme 更新dp[i]为剩下金额最优解+1
                    }
                }
            }
        }
        return dp[amount];//fixme 返回这个值的最优解
    }

    //fixme 解法教程: https://www.bilibili.com/video/BV1wD4y1d7hm?from=search&seid=2941701713750152698
    public int coinChangeEasy(int[] coins, int amount) {//fixme 找零钱问题，用动态规划解法
        int[] dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);//fixme 填充-1
        dp[0]=0;// dp[i] 代表最优解
        for(int currentAmount=1;currentAmount<=amount;currentAmount++){//fixme 变量i从1循环到amount,依次计算金额1到amount的最优解
            for (int coin:coins){
                int leftAmount=currentAmount-coin;
                //fixme 遇到直接跳过的，比如 coin=[2],amount 4=2+dp[2]--> amount 4=2+2+dp[0] 其实这个次数就是2 ：导致 dp[1],dp[3]还是初始化的-1，此时就continue即可
                if (leftAmount<0||dp[leftAmount]==Integer.MAX_VALUE) continue;
                dp[currentAmount]=Math.min(dp[leftAmount]+1,dp[currentAmount]);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];//fixme 返回这个值的最优解
    }
}
